package algorithm.recursionAndbacktrack.permuation.p46;

import java.util.ArrayList;
import java.util.List;

/**
 * 46. 全排列
 */
class Solution_v1 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums != null && nums.length > 0) {
            permute(res, new ArrayList<Integer>(), nums, 0);
        }
        System.out.println(res);
        return res;
    }

    // permutation中保存了一个有index个元素的排列
    // 向这个排列的末尾添加第index + 1个元素，获得一个index + 1个元素的排列
    public void permute(List<List<Integer>> res, List<Integer> permutation, int[] nums, int index) {
        if (index == nums.length) {
            res.add(new ArrayList<>(permutation));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!isInPermutation(nums[i], permutation)) {
                // 排除已经被选中为排列中的数
                permutation.add(nums[i]);
                permute(res, permutation, nums, index + 1);
                permutation.remove(permutation.size() - 1);
            }
        }
    }

    private boolean isInPermutation(int num, List<Integer> permutation) {
        for (int num1 : permutation) {
            if (num1 == num) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        new Solution_v1().permute(new int[] {1, 2, 3});
    }
}